from collections import Counter, deque

# 计算单词基因转换序列的长度
def wordGeneLength(beginWord: str, endWord: str, wordList: list[str]) -> int:
    # 工具方法：返回两个单词是否基因变化（即刚好只有一个字母不同）
    def isGeneChange(s: str, t: str) -> bool:
        return sum(a != b for a, b in zip(s, t)) == 1
    
    # 用字典表保存每个单词的最小演变次数
    # 初始化次数为0(默认)
    steps = Counter()

    # 创建队列，保存状态为当前搜索的单词
    queue = deque()
    queue.append(beginWord)

    # BFS - 基于队列开始搜索
    while queue:
        # 取出当前单词，记为s
        s = queue.popleft()
        # 从字典表取出当前长度，记为p
        p = steps[s]
        # 搜索下一个可以演变的单词
        for t in wordList:
            # 1. 判断是否新的目标点
            if steps[t] == 0 and isGeneChange(s, t):
                # 2. 判断是否已到达终点，是则直接返回
                if t == endWord:
                    return p + 1
                # 3. 计算保存目标点状态
                steps[t] = p + 1
                # 4. 将目标点状态放入队列尾部
                queue.append(t)

    # 没有结果返回-1
    return -1
# main
beginWord, endWord = 'hit', 'cog'
wordList = [ 'hot', 'dot', 'dog', 'log', 'cog' ]
ans = wordGeneLength(beginWord, endWord, wordList)
print('单词基因转换次数为:', ans)
